LeetCode 121. Best Time to Buy and Sell Stock (Easy)

題目連結

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

解題思路

❌ 直覺暴力解: 用兩個 for loop

function maxProfit(prices: number[]): number {
  let maxProfit: number = 0;
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      let profit = prices[j] - prices[i];
      if (profit > maxProfit) {
        maxProfit = profit;
      }
    }
  }
  return maxProfit;
}

這個方法用到兩個for loop，時間複雜度 O(n^2)，不是很好的解法

⭕ 正確的解題方向

1. 要找出最大的獲利，必需要買低賣高

2. sliding window:可以想成是一個區間，在根據情況來移動區間直到找到合適的值。類似下面這張圖

最佳解法

function maxProfit(prices: number[]): number {
  let max = 0;
  let left = 0;
  let right = 1;
  while (right < prices.length) {
    if (prices[left] < prices[right]) {
      let profit = prices[right] - prices[left];
      if (profit > max) {
        max = profit;
      }
    } else {
      left = right;
    }
    right++;
  }
  return max;
}

Complexity :

• Time: O(n)，n 是 prices 的長度
• Space: O(1)

解釋:

1. 先設最大值，和左右兩個邊界的位置
2. 接著使用 while loop 來走訪整個 array
3. 判斷之後的價錢是否高於之前的價錢，這樣才有獲利
4. 如果沒有的話就移動到下一個區間 (左邊界變成右邊界，右邊界往右移一格)
5. 如果有獲利且高於之前的最大獲利，將值換成最大獲利